package com.jdaw.datastructure.search;

import java.util.Arrays;

public class FibonacciSearch {
    public static int maxSize=20;
    public static void main(String[] args) {
        int[] arr={1,8,10,89,1000,1234};
        System.out.println(fibonacciSearch(arr,89));
    }

    //非递归
    public static int fibonacciSearch(int[] arr,int findVal){
        int low=0;
        int high=arr.length-1;
        int k=0;
        int mid=0;
        int[] f=fib();
        while(high>f[k]-1){
            k++;
        }
        //构造一个新的数组temp
        int[] temp= Arrays.copyOf(arr,f[k]);
        for(int i=arr.length;i<temp.length;i++){
            temp[i]=arr[arr.length-1];
        }
        while(low<=high){
            mid=low+f[k-1]-1;
            if(findVal<temp[mid]){
                high=mid-1;
                k--;
            }else if(findVal>temp[mid]){
                low=mid+1;
                k-=2;
            }else{
                if(mid<=high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }

    public static int[] fib(){
        int[] f=new int[maxSize];
        f[0]=1;
        f[1]=1;
        for(int i=2;i<maxSize;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }
}
